package org.thanos.demo.middle;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class InsertionSortList {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(1);
        listNode.next.next.next = new ListNode(3);
        System.out.println(insertionSortList(listNode));
    }

    public static ListNode insertionSortList(ListNode head) {
        if (Objects.isNull(head)) {
            return null;
        }
        List<Integer> list = new LinkedList<>();
        list.add(head.val);
        while (Objects.nonNull(head.next)) {
            list.add(head.next.val);
            head = head.next;
        }
        list.sort(Comparator.reverseOrder());
        ListNode last = new ListNode(list.get(0));
        list.remove(0);
        for (Integer i : list) {
            ListNode newNode = new ListNode(i);
            newNode.next = last;
            last = newNode;
        }
        return last;
    }

    public static ListNode insertionSortListBetter(ListNode head) {
        ListNode dummy = new ListNode(0), pre;
        dummy.next = head;

        while (head != null && head.next != null) {
            if (head.val <= head.next.val) {
                head = head.next;
                continue;
            }
            pre = dummy;

            while (pre.next.val < head.next.val) pre = pre.next;

            ListNode curr = head.next;
            head.next = curr.next;
            curr.next = pre.next;
            pre.next = curr;
        }
        return dummy.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
